package bintree.my_bin_tree;

import java.util.*;

/**
 * @Author: yuisama
 * @Date: 2021/9/4 12:02
 * @Description:二叉树基础问题
 * 二叉树的大部分问题，都可以看做是遍历问题的延续
 * 1.前序位置的代码只能通过函数参数获取父节点传递来的数据
 * 2.中序位置主要用在BST中，中序遍历BST就认为在遍历有序数组
 * 3.后续位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据
 * =》一旦发现题目是和子树相关，大概率要给函数设置合理的定义和返回值，在后续位置写代码解决问题
 */
public class BinTreeTest {

    private class TreeNode<E> {
        public E val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(E val) {
            this.val = val;
        }
    }

    // 生成一颗测试二叉树
    public TreeNode<Character> buildCharTree() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        TreeNode nodeI = new TreeNode('I');
        TreeNode nodeJ = new TreeNode('J');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeD.right = nodeF;
        nodeE.left = nodeG;
        nodeC.left = nodeH;
        nodeC.right = nodeI;
        nodeI.right = nodeJ;
        return nodeA;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    public void inOrder(TreeNode root) {
        if (root == null)
            return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    // 后续遍历
    public void postOrder(TreeNode root) {
        if (root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    // 莫里斯中序遍历法，不借助栈，O(1)时间复杂度遍历完整个树
    public void morrisInorder(TreeNode root) {
        while (root != null) {
            // 先访问左子树
            if (root.left != null) {
                TreeNode tmp = root.left;
                // 先找到左子树最右侧节点和当前树根建立起联系
                while (tmp.right != null && tmp.right != root) {
                    tmp = tmp.right;
                }
                // 若tmp.right == null,说明第一次访问到该节点，将当前左子树最右侧节点的右孩子连接到root
                if (tmp.right == null) {
                    tmp.right = root;
                    // 继续访问左子树
                    root = root.left;
                }else {
                    // 此时左子树遍历结束，访问根节点，继续走右子树
                    // 将tmp.right置空
                    System.out.print(root.val + " ");
                    root = root.right;
                    tmp.right = null;
                }
            }else {
                // 左树走完，访问根节点
                System.out.print(root.val + " ");
                // 继续访问右子树
                root = root.right;
            }
        }
    }

    // 层序遍历
    public List<List<Character>> levelOrder(TreeNode<Character> root) {
        // 结果集
        List<List<Character>> retList = new ArrayList<>();
        // 队列存储每层元素
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Character> level = new ArrayList<>();
            int n = queue.size();
            // 当前队列存储的是当前层的所有元素
            for (int i = 0; i < n; i++) {
                // 取得当前队列中的节点
                TreeNode<Character> node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            retList.add(level);
        }
        return retList;
    }

    // 获得一个二叉树节点个数
    public int getNodeSize(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + getNodeSize(root.left) + getNodeSize(root.right);
    }

    // 求二叉树叶子节点的个数
    // 求一个二叉树叶子节点个数 => 以root为根节点的左子树的叶子节点个数 + 以root为根的右子树叶子节点个数
    public int getLeafSize(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return 1;
        return getLeafSize(root.left) + getLeafSize(root.right);
    }

    // 当前节点的深度
    int depth;
    // 最大深度值
    int res;
    public int maxDepthByTraverse(TreeNode root) {
        traverse(root);
        return res;
    }

    /**
     * 思路一 : 遍历一遍二叉树得到答案的解
     * @param root
     */
    private void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序位置,进入二叉树节点之前更新当前节点的深度
        depth ++;
        if (root.left == null && root.right == null) {
            // 走到叶子节点，更新当前最大深度
            res = Math.max(res,depth);
        }
        traverse(root.left);
        traverse(root.right);
        // 后序位置，每当遍历完当前节点，深度--，表示返回父节点
        depth --;
    }

    /**
     * 思路二 : 通过分解问题计算出答案
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 先计算出左右两个子树的高度
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        // 后序位置
        return Math.max(leftDepth,rightDepth) + 1;
    }

    /**
     * 打印二叉树中每个节点的深度，根节点深度为1
     * 一个节点在第几层，从父节点传递来的信息就能获取记录清楚
     * 前序遍历即可
     * @param root
     */
    public void printNodeDepth(TreeNode root,int depth) {
        if (root == null) {
            return;
        }
        System.out.print("节点 " + root.val + "在第" + depth + "层");
        printNodeDepth(root.left,depth + 1);
        printNodeDepth(root.right,depth + 1);
    }

    /**
     * 以root为根的二叉树一共有多少个节点
     * 要获取到当前树的左右子树各有多少个节点，必须等子树遍历完才知道
     * 因此这个问题需要在后序位置获取函数的返回值才可
     * @param root
     * @return
     */
    public int nodeCounts(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftNodes = nodeCounts(root.left);
        int rightNodes = nodeCounts(root.right);
        // 后序位置，此时拿到了左右子树的节点个数
        System.out.print("节点 " + root.val + "一共有" + (leftNodes + rightNodes) + "个子节点");
        return leftNodes + rightNodes + 1;
    }

    // 在二叉树中查找元素
    public TreeNode find(TreeNode root,char toFind) {
        if (root == null)
            return null;
        if (root.val.equals(toFind))
            return root;
        // 在左子树中找
        TreeNode ret = find(root.left,toFind);
        if (ret != null)
            return ret;
        // 在右子树中找
        return find(root.right,toFind);
    }

    // 求二叉树第k层节点个数
    // k < 1，空树 ; k = 1 ,return 1
    // 要求第k层节点个数，问题转化为求以k-1层节点为根节点的左右子树的节点个数之和
    public int getKSize(TreeNode root,int k) {
        if (k < 1)
            return 0;
        if (k == 1)
            return 1;
        return getKSize(root.left,k - 1) + getKSize(root.right,k - 1);
    }

    // 判断一棵树是否为完全二叉树
    // 引入标志位在层序遍历二叉树的过程中，完全二叉树一共有两种状态
    // 1.任何一个节点都有左右子树，直到遇到任意一个节点为叶子节点或只有左子树进入第二状态
    // 2.在进入第二状态后，剩下的所有节点均为叶子节点
    public boolean isCompleteTree(TreeNode root) {
        if (root == null)
            return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isSecond = false;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 还在第一阶段
            if (!isSecond) {
                if (node.left != null && node.right != null) {
                    // 将左右子树入队列，继续判定
                    queue.offer(node.left);
                    queue.offer(node.right);
                }else if (node.right != null && node.left == null) {
                    // 此时节点只有右子树而无左子树，不符合完全二叉树定义，直接返回false
                    return false;
                }
                else if (node.left != null && node.right == null) {
                    // 此时发现该节点只有左树，将左树入队列，并且将状态置为第二阶段
                    queue.offer(node.left);
                    isSecond = true;
                }else {
                    // 此时为叶子节点，进入第二阶段
                    isSecond = true;
                }
            }else {
                // 进入第二阶段,所有节点均为叶子节点，
                // 当发现一个非叶子节点时，都不是完全二叉树，直接返回false
                if (node.left != null || node.right != null)
                    return false;
            }
        }
        // 遍历所有节点后都没有找到反例，该树符合完全二叉树定义
        return true;
    }


    public static void main(String[] args) {
        // 生成一颗测试树
        BinTreeTest binTreeTest = new BinTreeTest();
        TreeNode<Character> testTree = binTreeTest.buildCharTree();
        System.out.println("二叉树高度为 : " + binTreeTest.maxDepthByTraverse(testTree));
//        System.out.println("前序遍历结果为:------------------");
//        binTreeTest.preOrder(testTree);
//        System.out.println("-------------------------------");

//        System.out.println("中序遍历结果为:");
//        binTreeTest.inOrder(testTree);
//        System.out.println();
//        System.out.println("-------------------------------");
//
//        System.out.println("莫尔斯中序遍历结果为:");
//        binTreeTest.morrisInorder(testTree);


//        System.out.println("后序遍历结果为:------------------");
//        binTreeTest.postOrder(testTree);
//        System.out.println("-------------------------------");
//
//        System.out.println("层序遍历结果为:------------------");
//        System.out.println(binTreeTest.levelOrder(testTree));
//        System.out.println("-------------------------------");
//
//        System.out.println("该树一共有 " + binTreeTest.getNodeSize(testTree) + "个节点");
//
//        System.out.println("该树共有 " + binTreeTest.getLeafSize(testTree) + " 个叶子节点");
//
//        System.out.println("该树第3层共有 " + binTreeTest.getKSize(testTree,3) + " 个节点");
//
//        System.out.println("该树节点值为F的节点为 " + binTreeTest.find(testTree,'Z'));
    }
}
